% CSC343 Assignment 3
% aut Caroline Liu
% aut Kasra Kyanzadeh
% due 2013/04/05


\documentclass[11pt,letterpaper]{article}

\usepackage[latin1]{inputenc}
\usepackage[hmargin=0.7in, top=0.8in, bottom=1in, headsep=.3in, footskip=.4in]{geometry}
\usepackage{enumitem}     % for fancy enumerations
\usepackage{textcomp}     % for arrow ->
\usepackage{multicol}     % for page columns
\usepackage{multirow}     % for table rows
\usepackage{color}        % for color


% macros
\newcommand*{\cl}{$^{+}$}                      % shortcut for ^+ closure superscript
\newcommand*{\mb}[2]{{#1$_{#2}$}$^{+}$}        % format for minimal basis LHS: A_{S-1,2,3}^+
\newcommand*{\arr}{\textrightarrow}            % shortcut for -> arrow
\newcommand{\todo}[1]{\colorbox{green}{#1}}    % todo marker

% first-level list: numeric -- 1., 2., 3.
\newenvironment*{questions}
{\begin{enumerate}
   [label=\arabic*., itemsep=20pt]
   }
{\end{enumerate}}

% second-level list: alpha -- a), b), c)
\newenvironment*{subquestions}
{\begin{enumerate}
   [label=\alph*), itemsep=14pt, parsep=7pt]
   }
{\end{enumerate}}


\begin{document}

    % heading
    \begin{center}
        {April 5, 2013} \\[2pt]
        {\LARGE CSC343 Assignment 3 Part 3} \\[2pt]
        {\large Kasra Kyanzadeh (g2kk)} \\
        {\large Caroline Liu (c1liucar)} \\
    \end{center}

    % content
    \begin{questions}
        \item
        \begin{subquestions}
            \item
            Compute the closure of each FD:
    
            \begin{itemize}
                \item B\cl = BCDAG
                \item BF\cl = BFHCDAG
                \item C\cl = CAG
                \item CEH\cl = CEHFBDAG (Superkey)
                \item CH\cl = CHBDAG
            \end{itemize}
            
            Therefore, B\arr CD, BF\arr H, C\arr AG, and CH\arr B violate BCNF because they are not superkeys for the relation.
                
            \item
            Start with R = ABCDEFGH.
                
            B\arr CDAG (from the closure calculated above) violates BCNF, so we split R into two relations, R1 and R2. R1 contains all the attributes that B functionally determines, while R2 contains B and the remaining attributes. Including B in both relations ensures that R1 and R2 can be joined losslessly.
            \begin{itemize}
                \item R1 = BCDAG
                \item R2 = BEFH
            \end{itemize}
  
            \textit{Check R1.}
            First, we project R's FDs onto R1. R1 has the FDs B\arr ACDG and C\arr AG. C\arr AG violates BCNF, because C does not functionally determine all attributes in R1. So we split R1 in the same way we did for R:
            
            \begin{itemize}
                \item R3 = BCD
                \item R4 = CAG
            \end{itemize}
            
            R3 and R4 both satisfy BCNF, because the LHS of their FDs are superkeys. R3 has the FD B\arr CD, while R4 has C\arr AG.
            
            \textit{Check R2.}
            R2 has the FD BF\arr H. This FD violates BCNF, as BF does not functionally determine E. So, we split R2, including BF in both relations:
            
            \begin{itemize}
                \item R5 = BFE
                \item R6 = BFH
            \end{itemize}
            
            Here, R5 has no non-trivial FD; its key is BFE. R6 only has the FD BF\arr H, so BF is a key. Thus, both R5 and R6 satisfy BCNF. At this point, the decomposition is complete.
            
            The final decomposition consists of the following relations:
            
            \begin{tabular}{|l|l|}
                \hline
                Relation & Non-trivial FDs \\
                \hline
                R3 = BCD & B\arr CD \\
                R4 = CAG & C\arr AG \\
                R5 = BFE & \o \\
                R6 = BFH & BF\arr H \\
                \hline
            \end{tabular}
                
            \item
            No, this decomposition is not dependency-preserving. For example, consider R's FD CEH\arr F. We also know that in R, CEH is a superkey -- it functionally determines ABCDEFGH. Consider the following instance of R:
            
            \begin{tabular}{|llllllll|}
                \hline
                A & B & C & D & E & F & G & H \\
                \hline
                - & o & i & q & j & m & - & k \\
                - & p & i & r & j & n & - & k \\
                \hline
            \end{tabular} \\
            
            Note that this instance violates CEH\arr F because the tuples have the same values for CEH, but different values for F. Similarly, the tuples also fail to agree on B and D, even though it should be the case that CEH\arr BD in R.
            
            However, this invalid instance of R can be derived by joining the following valid instances of the decomposed relations:
            
            \begin{multicols}{4}
            \begin{tabular}{|lll|}
                \multicolumn{3}{l}{R3} \\
                \hline
                B & C & D \\
                \hline
                o & i & q \\
                p & i & r \\ 
                \hline
            \end{tabular}
            
            \begin{tabular}{|lll|}
                \multicolumn{3}{l}{R4} \\
                \hline
                C & A & G \\
                \hline
                i & - & - \\ 
                \hline
            \end{tabular}
            
            \begin{tabular}{|lll|}
                \multicolumn{3}{l}{R5} \\
                \hline
                B & F & E \\
                \hline
                o & m & j \\
                p & n & j \\ 
                \hline
            \end{tabular}
            
            \begin{tabular}{|lll|}
                \multicolumn{3}{l}{R6} \\
                \hline
                B & F & H \\
                \hline
                o & m & k \\
                p & n & k \\ 
                \hline
            \end{tabular}
            \end{multicols}
            
            Since none of these instances violate the FDs of the decomposed relations, CEH\arr FBD is not preserved. 
            
            Therefore, the decomposition does not preserve all of the original FDs.
                
        \end{subquestions}
        
        \item 
        \begin{subquestions}
            \item 
            First, we compute the closure of each FD:
            
            \begin{itemize}
                \item A\cl = ABCDEFGH
                \item ACF\cl = ABCDEFGH
                \item AD\cl = ABCD
                \item BCG\cl = BCDG
                \item CF\cl = ABCDEFGH
                \item CH\cl = CBDEGH
                \item D\cl = BD
                \item H\cl = BDEG
            \end{itemize}
            
            A and CF are keys for R, as they uniquely determine tuples in R. Furthermore, A and CF cannot be further reduced. (ACF also uniquely determines tuples in R, but it can be reduced to the keys A and CF.)
            
            \item
            Let $S$ be the set of all the non-trivial FDs of R, with only one attribute on the RHS. These FDs are listed below:
            
            \begin{multicols}{4}
            \begin{enumerate}[label=(\arabic*)]
                \item A\arr C
                \item A\arr D
                \item ACF\arr G % rm
                \item AD\arr B % rm
                \item AD\arr E % rm
                \item AD\arr F
                \item BCG\arr D
                \item CF\arr A
                \item CF\arr H
                \item CH\arr G
                \item D\arr B
                \item H\arr D
                \item H\arr E
                \item H\arr F
            \end{enumerate}
            \end{multicols}
            
            For each FD in $S$, we compute the closure of its LHS, without that FD (and any other FDs we have removed from S at that point). 
            
            \begin{tabular}{lll}
                \mb{A}{S-\{1\}} & = ADBEF & Could not get C without A\arr C. \\
                \mb{A}{S-\{2\}} & = AC & Could not get D without A\arr D. \\
                \mb{ACF}{S-\{3\}} & = ACFDBEHG & Got G without ACF\arr G. Remove (3). \\
                \mb{AD}{S-\{3,4\}} & = ADCEFGHB & Got B without AD\arr B. Remove (4). \\
                \mb{AD}{S-\{3,4,5\}} & = ADCBFGHE & Got E without AD\arr E. Remove (5). \\
                \mb{AD}{S-\{3,4,5,6\}} & = ADCBE & Could not get F without AD\arr F. \\
                \mb{BCG}{S-\{3,4,5,7\}} & = BCG & Could not get D without BCG\arr D. \\
                \mb{CF}{S-\{3,4,5,8\}} & = CFHGDEB & Could not get A without CF\arr A. \\
                \mb{CF}{S-\{3,4,5,9\}} & = CFADGB & Could not get H without CF\arr H. \\
                \mb{CH}{S-\{3,4,5,10\}} & = CHDEFB & Could not get G without CH\arr G. \\
                \mb{D}{S-\{3,4,5,11\}} & = D & Could not get B without D\arr B. \\
                \mb{H}{S-\{3,4,5,12\}} & = HEF & Could not get D without H\arr D. \\
                \mb{H}{S-\{3,4,5,13\}} & = HDFB & Could not get E without H\arr E. \\
                \mb{H}{S-\{3,4,5,14\}} & = HDEB & Could not get F without H\arr F. \\
            \end{tabular} \\

            We are now left with the following FDs:

            \begin{multicols}{4}
            \begin{enumerate}[label=(\arabic*)]
                \item A\arr CD
                \item AD\arr F
                \item BCG\arr D
                \item CF\arr AH
                \item CH\arr G
                \item D\arr B
                \item H\arr DEF
            \end{enumerate}
            \end{multicols}

            For each of these remaining FDs that have more than one attribute on the LHS, we check whether the FD still holds if we remove an attribute from the LHS:
            
            \begin{tabular}{lll}
                A\cl & = ABCDEFGH & Got F! Simplify AD\arr F to A\arr F. \\
                B\cl & = B & Could not get D with just B. Keep BCG\arr D. \\
                C\cl & = C & Could not get D with just C. Keep BCG\arr D. \\
                G\cl & = G & Could not get D with just G. Keep BCG\arr D. \\
                C\cl & = C & Could not get A or H with just C. Keep CF\arr AH. \\
                F\cl & = F & Could not get A or H with just F. Keep CF\arr AH. \\
                C\cl & = C & Could not get G with just C. Keep CH\arr G. \\
                H\cl & = HDEFB & Could not get G with just H. Keep CH\arr G. \\
            \end{tabular} \\
            
            We now have the following FDs (with A\arr CD and A\arr F collapsed into one FD):
            
            \begin{itemize}
                \item A\arr CDF
                \item BCG\arr D
                \item CF\arr AH
                \item CH\arr G
                \item D\arr B
                \item H\arr DEF
            \end{itemize}
    
            This is our minimal basis, as we cannot split the LHS of any FD.
            
            \pagebreak
            \item 
            Each FD in our minimal basis becomes a relation under the 3NF algorithm:
            
            \begin{tabular}{ll}
                A\arr CDF: & R1 = ACDF \\
                BCG\arr D: & R2 = BCDG \\
                CF\arr AH: & R3 = ACFH \\
                CH\arr G: & R4 = CGH \\
                D\arr B: & R5 = BD \\
                H\arr DEF: & R6 = DEFH \\
            \end{tabular} \\
            
            The original superkeys A and CF are both in some relation, so these are all the relations we need.
            
            \item
            Yes, this schema does allow redundancy. For example, we see that attributes ACF are both in R1 and R3, even though ACF is not a key -- we could just have the key A, and join on that single attribute instead. CF is therefore redundant in one of the relations. However, we keep CF in both relations to preserve R's functional dependencies.
            
        \end{subquestions}
    \end{questions}

\end{document}